The Internet has transformed the world into a global marketplace. For example, a person anywhere in the world may buy or sell goods to anyone else. Given such convenience, online applications such as auctions, multi-player games and social networks engender a huge potential market and consequently attract a lot of attention. Unfortunately, malicious behavior, such as account hijacking and non-delivery of goods in online auctions, introduces risks.
To prevent such risks, online applications employ reputation systems that rely on user-assigned scores to judge on other users' legitimate behavior. For example, a buyer in an online auction system may use the seller's score of the reputation system to judge whether the seller is trustworthy. However, a serious problem of existing reputation systems is the simplicity to create a highly trustworthy score by a seller himself or a seller's friend, or vice versa, create an untrustworthy score for a competitor. Since adversaries may apply several accounts to complete several faked transactions, foiling existing reputation systems is often straightforward.
Many approaches for addressing these challenges have been discussed. For example, Zhang et al. and Pandit et al. use a transaction network model to analyze auction fraud. In their model, they establish an undirected transaction graph where each node denotes a registered user and each edge indicates a completed transaction between the two users. By cooperating with other mathematical models and algorithms, they may identify potentially fraudulent users. Kuo et al. use reputation network constructed from buyer's feedbacks to identify fraudulent users.
Pujol et al. and Sabater et al. extract reputation by means of social network. Also, Hogg et al. summarize the reputation systems constructed via online social network. The online social network is automatically constructed from any observable internet interaction, such as the referred web links and emails in the homepages, and the relationships established in the social networking websites (e.g., facebook). These online relationships contribute online social network. This type of reputation system may enhance the effectiveness of the rating. Swamynathan et al. also shows that this type of reputation system is more trustful and satisfied than feedback reputation systems. Besides that, the notion to evaluate a user using social network may be applicable to other applications, such as Voice over IP (VoIP), Internet Message (IM), peer to Peer (P2P) and Reliable Email (RE). RE proposed by Freeman et al. considers privacy issue.
Although reputation systems have been proposed for solving these problems, most reputation systems in applications are still unreliable. Reputation systems also pose some privacy problems. For example, they may reveal private information of users. They would not achieve real reliability or being trustworthy if the online social relationship is not related to personal social relationship. Also, a forging problem may occur if an online social relationship is also not cryptographically verifiable. On the other hand, most of these systems reveal private personal information.
Social network represents relationships within a community. Several types of social network may be established according to different social relationship such as kinship, friendship, cooperation, etc.
Recently, research on private matching receives a lot of attention and several schemes and applications are proposed. Assuming there are two databases A and B, one query QεA and one matching protocol computes P=Q∩B. The scheme is secure and preserving privacy if it satisfies the following requirements. (1) Privacy: Each party can know only P and it's input to the matching protocol. Except for this information, each party learns nothing. (2) Non-spoofable: Items in A and B are really authorized by item owners. This means that the user may make query Q only if the owners of these items authorize and give the user these items. In other words, the user can not generate the queried items without authorization of the item owners. Besides that, the user should have some proofs to demonstrate that the item owner authorizes the user.
In Hash Protocol (HP), a person, who wants to query the common items in the other's database, computes hash values of items in his own database. Then he and the target exchange these hash values. By this way, they may find the common items without revealing the information of the un-matched items. On the other hand, Agrawal et al. proposed AgES which uses commutative encryption to achieve private matching. Freedman et al. proposed a polynomial-based private matching scheme. They use the property of homomorphic encryption to achieve better privacy. A variant of their scheme, set cardinality private matching, let databases A know only the cardinality of Q∩B, not the actual items in this set. After that, Kissner and Song extend FNP scheme to support more functionality. HP, AgES and Freedman et al's schemes are categorized to asymmetric exchange of information, different from symmetric exchange in which both parties know the same information in the protocols.
Besides those, Li et al. proposed Data Ownership Certificate (DoC) to ensure non-spoofable. If the user does not obtain the item and the corresponding DoC, he can not make the query and convince the other.